{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Nth Magical Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nthMagicalNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #第 N 个神奇数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个正整数如果能被 <code>a</code> 或 <code>b</code> 整除，那么它是神奇的。</p>\n",
    "\n",
    "<p>给定三个整数 <code>n</code> ,&nbsp;<code>a</code> , <code>b</code> ，返回第 <code>n</code> 个神奇的数字。因为答案可能很大，所以返回答案&nbsp;<strong>对&nbsp;</strong><code>10<sup>9</sup>&nbsp;+ 7</code> <strong>取模&nbsp;</strong>后的值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, a = 2, b = 3\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, a = 2, b = 3\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>2 &lt;= a, b &lt;= 4 * 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [nth-magical-number](https://leetcode.cn/problems/nth-magical-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [nth-magical-number](https://leetcode.cn/problems/nth-magical-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n2\\n3', '4\\n2\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:        \n",
    "    def nthMagicalNumber(self, N, A, B):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type A: int\n",
    "        :type B: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        left = min(A, B)\n",
    "        right = int((10 ** 9) * left)\n",
    "        \n",
    "        gcd = self.get_gcd(A, B)\n",
    "        lcm = int(A * B / gcd)\n",
    "        \n",
    "        while left < right:\n",
    "            mid = left + ((right - left) >> 1)\n",
    "            cur = int(mid / A) + int(mid / B) - int(mid / lcm)\n",
    "            if cur == N:\n",
    "                return max(A * int(mid / A), B * int(mid / B)) % (10 ** 9 + 7)\n",
    "            elif cur < N:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        return max(A * int(left / A), B * int(left / B)) % (10 ** 9 + 7)\n",
    "    \n",
    "    def get_gcd(self, b, a):\n",
    "        while a:\n",
    "            a, b = b % a, a\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lcm = a * b // math.gcd(a, b)\n",
    "        return bisect.bisect_left(range(min(a, b) * n + 1), n, key=lambda x: x // a + x // b - x // lcm) % (\n",
    "                10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lcm = math.lcm(a, b)\n",
    "        left, right = 0, min(a, b) * n  # 开区间 (left, right)\n",
    "        while left + 1 < right:  # 开区间不为空\n",
    "            mid = (left + right) // 2\n",
    "            if mid // a + mid // b - mid // lcm >= n:\n",
    "                right = mid  # 范围缩小到 (left, mid)\n",
    "            else:\n",
    "                left = mid  # 范围缩小到 (mid, right)\n",
    "        return right % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        #a b 的最小公倍数\n",
    "        x = a*b//gcd(a,b)\n",
    "        l,r = 0,min(a,b)*n \n",
    "        while l + 1 < r:\n",
    "            mid = (l + r) >> 1\n",
    "            if mid // a + mid // b - mid//x >= n:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return r % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        mod = 1000000007\n",
    "        if a == b: return (n * a) % mod\n",
    "        if a < b:\n",
    "            tmp = a\n",
    "            a = b\n",
    "            b = tmp\n",
    "        def gcd(a, b):\n",
    "            if a < b:\n",
    "                tmp = a\n",
    "                a = b\n",
    "                b = tmp\n",
    "            if a % b == 0: return b\n",
    "            return gcd(b, a % b)\n",
    "        d = gcd(a, b)\n",
    "        c = a // d * b\n",
    "        h, t = 0, n\n",
    "        while h < t:\n",
    "            m = (h + t) // 2\n",
    "            cnt1, cnt2 = (m * a) // b, (m * a) // c\n",
    "            if cnt1 - cnt2 + m < n: h = m + 1\n",
    "            else: t = m\n",
    "        # return h, a, b, (h * a) // b - (h * a) // c + h\n",
    "        if t == 0: return (b * n) % mod\n",
    "        val = (h * a) // b - (h * a) // c + h\n",
    "        if val == n: return (h * a) % mod\n",
    "        if val > n:\n",
    "            h -= 1\n",
    "            val = (h * a) // b - (h * a) // c + h\n",
    "        diff = n - val\n",
    "        return (((h * a) // b + diff) * b) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lcm = math.lcm(a, b)\n",
    "        def check(mid):\n",
    "            return mid // a + mid // b - mid // lcm >=n\n",
    "        l, r = min(a, b), min(a, b) * n\n",
    "        while l + 1 < r:\n",
    "            mid = l + (r-l) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return r % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        lcm = math.lcm(a, b)\n",
    "        left, right = 0, min(a,b) * n\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid // a + mid // b - mid // lcm >= n:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right % MOD\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        def gcd(a,b):\n",
    "            return a if b==0 else gcd(b,a%b)\n",
    "        def lcm(a,b):\n",
    "            return max(a,b)//gcd(a,b)*min(a,b)\n",
    "        l,r = 0,min(a,b)*n\n",
    "        ans = 0\n",
    "        while l<=r:\n",
    "            m = (l+r)//2\n",
    "            if m//a + m//b -m//lcm(a,b) >= n:\n",
    "                ans = m\n",
    "                r = m-1\n",
    "            else:\n",
    "                l = m+1\n",
    "        return ans%(10**9+7)            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        #公倍数函数 a*b//gcd(a,b)\n",
    "        #二分查找答案\n",
    "        #上下限 lcm(a,b)*n\n",
    "        #检查函数 a的数量+b的数量-lcm(a,b)的数量\n",
    "        MOD=10**9+7\n",
    "\n",
    "        def check(a:int,b:int,c:int,t:int,n:int)->bool:\n",
    "            tot=t//a+t//b-t//c\n",
    "            return tot>=n\n",
    "\n",
    "        c=lcm(a,b)\n",
    "        l,r=0,min(a,b)*n\n",
    "        while l+1<r:\n",
    "            m=l+(r-l)//2\n",
    "            if(check(a,b,c,m,n)): r=m\n",
    "            else: l=m\n",
    "        \n",
    "        return r%MOD\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        if a >= b:\n",
    "            x, y = a, b\n",
    "        else:\n",
    "            x, y = b, a\n",
    "        def gcd(x, y):\n",
    "            return x if y == 0 else gcd(y, x % y)\n",
    "        def lcm(x, y):\n",
    "            return x // gcd(x, y) * y\n",
    "        left, right = 1, y * n + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2 \n",
    "            if mid // x + mid // y - mid // lcm(x, y) >= n:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lcm = math.lcm(a, b)\n",
    "        l, r = 0, max(a,b)* n\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if (mid // a + mid // b - mid //lcm) >= n:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 1000000007\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lcm = math.lcm(a,b)\n",
    "        ok = lambda m: m//a+m//b-m//lcm >= n\n",
    "        return bisect_left(range(min(a,b)*n),True,key = ok)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        l = min(a, b)\n",
    "        r = n * l\n",
    "        c = lcm(a, b)\n",
    "\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "\n",
    "            cnt = mid // a + mid // b - mid // c\n",
    "\n",
    "            if cnt >= n:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "            \n",
    "        return (r + 1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 1000000007\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lcm = math.lcm(a,b)\n",
    "        return bisect_left(range(min(a,b)*n),True,key = lambda m: m//a+m//b-m//lcm >= n)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        #公倍数函数 a*b//gcd(a,b)\n",
    "        #二分查找答案\n",
    "        #上下限 lcm(a,b)*n\n",
    "        #检查函数 a的数量+b的数量-lcm(a,b)的数量\n",
    "        lcm = math.lcm(a, b)\n",
    "        return bisect_left(range(min(a, b) * n), n, key=lambda x: x // a + x // b - x // lcm) % (10 ** 9 + 7)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        def gcd(x: int, y: int) -> int:\n",
    "            if x < y:\n",
    "                return gcd(y, x)\n",
    "            if y == 0:\n",
    "                return x\n",
    "            return gcd(y, x % y)\n",
    "\n",
    "        def lcm(x: int, y: int) -> int:\n",
    "            # 最小公倍数就是乘积除以最大公因数\n",
    "            return x * y // gcd(x, y)\n",
    "\n",
    "        # 二分x（第n个神奇数字）, 计算<=x的神奇数字的个数\n",
    "        lcm = lcm(a, b)\n",
    "        left, right = 0, min(a, b) * n  # 开区间 (left, right)\n",
    "        while left + 1 < right:  # 开区间不为空\n",
    "            mid = (left + right) // 2\n",
    "            # 数字再变小一点，也有可能有N个\n",
    "            if mid // a + mid // b - mid // lcm >= n:\n",
    "                right = mid  # 范围缩小到 (left, mid)\n",
    "            else:\n",
    "                left = mid  # 范围缩小到 (mid, right)\n",
    "        return right % (10 ** 9 + 7)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            if b == 0:\n",
    "                return a\n",
    "            return gcd(b, a % b)\n",
    "        \n",
    "        def lcm(a, b):\n",
    "            return a * b // gcd(a, b)\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        c = lcm(a, b)\n",
    "        l, r = min(a, b), n * min(a, b)\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            cnt = mid // a + mid // b - mid // c\n",
    "            if cnt >= n:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        l = min(a, b)\n",
    "        r = n * min(a, b)\n",
    "        c = lcm(a, b)\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            cnt = mid // a + mid // b - mid // c\n",
    "            if cnt >= n:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return (r + 1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lcm = math.lcm(a, b)\n",
    "        left, right = 0, min(a, b) * n  # 开区间 (left, right)\n",
    "        while left + 1 < right:  # 开区间不为空\n",
    "            mid = (left + right) // 2\n",
    "            if mid // a + mid // b - mid // lcm >= n:\n",
    "                right = mid  # 范围缩小到 (left, mid)\n",
    "            else:\n",
    "                left = mid  # 范围缩小到 (mid, right)\n",
    "        return right % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        lc = lcm(a, b)\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        r = n * min(a,b)\n",
    "        m = 0\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            cnt = m // a + m // b - m // lc\n",
    "            if cnt >= n:\n",
    "                ans = m\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lcm = math.lcm(a, b)\n",
    "        def check(mid):\n",
    "            return mid // a + mid // b - mid // lcm >=n\n",
    "        l, r = 0, min(a, b) * n\n",
    "        while l + 1 < r:\n",
    "            mid = l + (r-l) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return r % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lcm = math.lcm(a, b)\n",
    "        left, right = 0, min(a, b) * n  # 开区间 (left, right)\n",
    "        while left + 1 < right:  # 开区间不为空\n",
    "            mid = (left + right) // 2\n",
    "            if mid // a + mid // b - mid // lcm >= n:\n",
    "                right = mid  # 范围缩小到 (left, mid)\n",
    "            else:\n",
    "                left = mid  # 范围缩小到 (mid, right)\n",
    "        return right % (10 ** 9 + 7)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcd(a,b):\n",
    "        if b == 0:\n",
    "            return a\n",
    "        return gcd(b,a % b)\n",
    "    def lcm(a,b):\n",
    "        return (a / gcd(a,b) * b)\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lc = lcm(a,b)\n",
    "        l = min(a,b)\n",
    "        r = n * min(a,b)\n",
    "        ans = -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) >> 1\n",
    "            if (mid//a + mid//b - mid//lc) >= n:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return (r + 1) % int(1e9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lab = a * b // gcd(a, b)\n",
    "        l, r = 0, int(1e18)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mid // a + mid // b - mid // lab < n:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        lcm_ = lcm(a, b)\n",
    "\n",
    "\n",
    "        def check(x):\n",
    "            return x // a + x // b - x // lcm_ >= n\n",
    "        \n",
    "        l, r = 1, min(a, b) * n\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return l % mod\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        # 复习灵神思路\n",
    "        # 问题替换 & 容斥原理 & 二分查找\n",
    "        # tips：把n当成目标值\n",
    "        lcm = math.lcm(a, b)\n",
    "        left, right = 0, min(a, b) * n\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid // a + mid // b - mid // lcm >= n:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        c = math.lcm(a,b)#求最小公倍数,重复计算\n",
    "        l = min(a,b)\n",
    "        r = n*(min(a,b))+1 #上界\n",
    "        #寻找左边界\n",
    "        while l < r:\n",
    "            mid = (l + r) //2\n",
    "            sum_n = (mid//a) + (mid//b) -(mid//c)\n",
    "            if sum_n >= n: #缩小右边界\n",
    "                r = mid\n",
    "            elif sum_n <n:\n",
    "                l = mid + 1\n",
    "        return l% (10 ** 9 + 7)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zxgbs(self,a,b):\n",
    "        if a%b==0:\n",
    "            return b\n",
    "        else:return self.zxgbs(a,(a%b))\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        # a,b = max(a,b),min(a,b)\n",
    "        gongbei = math.lcm(a, b)\n",
    "        i,j = 0,min(a,b)*n\n",
    "        while i + 1 < j:  # 开区间不为空\n",
    "            mid = (i + j) // 2\n",
    "            if mid // a + mid // b - mid // gongbei >= n:\n",
    "                j = mid \n",
    "            else:\n",
    "                i = mid  #\n",
    "        return j % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        # 最大公因子\n",
    "        lm = math.lcm(a,b)\n",
    "        # 二分\n",
    "        left = 1\n",
    "        right = min(a,b)*n\n",
    "        while left <= right:\n",
    "            mid =(right+left)//2\n",
    "            if (mid//a+mid//b-mid//lm) >= n:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left%mod\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lcm = math.lcm(a, b)\n",
    "        left, right = 1, min(a, b) * n\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid // a + mid // b - mid // lcm >= n:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lcm = math.lcm(a, b)\n",
    "        left, right = 0, min(a, b) * n \n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid // a + mid // b - mid // lcm >= n:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        # 能被a,b整除的数字是神奇的\n",
    "        # 返回神奇列表当中的第i个\n",
    "        min_bei = a*b//math.gcd(a,b)\n",
    "        def check(n):\n",
    "            return n//a + n//b - n//min_bei \n",
    "        left = 0 \n",
    "        right = 10**30+1 \n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left+right) >> 1\n",
    "            k = check(mid)\n",
    "            if k == n:\n",
    "                mid -= min(mid%a,mid%b,mid%min_bei)\n",
    "                return mid%(10**9+7)\n",
    "            elif k > n:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            return a if b == 0 else gcd(b, a % b)\n",
    "\n",
    "        def lcm(a, b):\n",
    "            return a // gcd(a, b) * b\n",
    "\n",
    "        lcm_ab = lcm(a, b)\n",
    "        ans = 0\n",
    "        # l = 0\n",
    "        # r = n * min(a, b)\n",
    "        # l......r\n",
    "        l, r = 0, n * min(a, b)\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            # 1....m\n",
    "            if m // a + m // b - m // lcm_ab >= n:\n",
    "                ans = m\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "\n",
    "        return ans % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import lcm\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        c = lcm(a, b)\n",
    "        x1 = min(a, b)\n",
    "        x2 = n * min(a, b)\n",
    "        while x1 <= x2:\n",
    "            x3 = (x1 + x2) // 2\n",
    "            m = x3 // a + x3 // b - x3 // c\n",
    "            if n > m:\n",
    "                x1 = x3 + 1\n",
    "            elif n <= m:\n",
    "                x2 = x3 - 1\n",
    "        return (x2 + 1) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "class Solution:\r\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\r\n",
    "\r\n",
    "        Mod=10**9+7\r\n",
    "        c=math.lcm(a,b)\r\n",
    "        m=c//a+c//b-1\r\n",
    "        r=n%m\r\n",
    "        res=(c*(n//m))%Mod\r\n",
    "        if r==0:\r\n",
    "            return res\r\n",
    "        add_a=a\r\n",
    "        add_b=b\r\n",
    "        r-=1\r\n",
    "        while r>0:\r\n",
    "            if add_a<=add_b:\r\n",
    "                add_a+=a\r\n",
    "            else:\r\n",
    "                add_b+=b\r\n",
    "            r-=1\r\n",
    "        return (res+min(add_a,add_b))%Mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        c = lcm(a, b)\n",
    "        r = (a + b) * n\n",
    "        return bisect_left(range(r), x=n, key=lambda x: x // a + x // b - x // c) % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lcm = math.lcm(a, b)\n",
    "        left, right = 0, min(a, b) * n\n",
    "        while left + 1 < right:\n",
    "            mid  = (left + right) >> 1\n",
    "            if mid // a + mid // b - mid // lcm >= n:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        l = min(a, b)\n",
    "        r = n * min(a, b)\n",
    "        c = lcm(a, b)\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            cnt = mid // a + mid // b - mid // c\n",
    "            if cnt < n:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return r % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        minNum, maxNum = (a, b) if a < b else (b, a)\n",
    "        left = minNum\n",
    "        right = minNum * n\n",
    "        tem = minNum * maxNum / math.gcd(minNum, maxNum)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            minCnt = mid // minNum\n",
    "            maxCnt = mid // maxNum\n",
    "            commCnt = mid // tem\n",
    "            cnt = minCnt + maxCnt - commCnt\n",
    "            if cnt < n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                if cnt == n:\n",
    "                    return max(minCnt * minNum, maxCnt * maxNum) % (10 ** 9 + 7)\n",
    "                right = mid - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        l = min(a, b)\n",
    "        r = n * min(a, b)\n",
    "        c = lcm(a, b)\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            cnt = mid // a + mid // b - mid // c\n",
    "            if cnt >= n:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return (r + 1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        if a > b:\n",
    "            a, b = b, a\n",
    "        \n",
    "\n",
    "        \"\"\"\n",
    "        a < b\n",
    "        \"\"\"\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        if b % a == 0:\n",
    "            return n * a % MOD\n",
    "        \n",
    "        # T = a + b - 1\n",
    "        # k, r = n // T, n % T\n",
    "        # print(k, r, T)\n",
    "\n",
    "        lcm = math.lcm(a, b)\n",
    "\n",
    "        lb, la = lcm // a, lcm // b\n",
    "        T = lb + la - 1\n",
    "        k, r = n // T, n % T\n",
    "\n",
    "\n",
    "        if r == 0:\n",
    "            return lcm * k % MOD\n",
    "\n",
    "        # 找第r个\n",
    "        # 1 ... a-1\n",
    "        # 1 ... b-1\n",
    "\n",
    "        \n",
    "\n",
    "        def getKth(k):\n",
    "            # 从两个sorted list中拿到第k个元素\n",
    "\n",
    "            idx1 = idx2 = 1\n",
    "\n",
    "            while True:\n",
    "                # 退出条件\n",
    "                if idx1 == lb:\n",
    "                    # idx2 * b ... (idx2 + k - 1)*b\n",
    "                    return (idx2 + k - 1)*b\n",
    "                if idx2 == la:\n",
    "                    return (idx1 + k - 1)*a\n",
    "                if k == 1:\n",
    "                    return min(idx1*a, idx2*b)\n",
    "                \"\"\"\n",
    "                idx1 ... idx1 + k // 2 - 1 -- k // 2 - 1 个数字\n",
    "                idx2 ... idx2 + k // 2 - 1\n",
    "                \"\"\"\n",
    "\n",
    "                n1 = min(idx1 + k // 2 - 1, lb)\n",
    "                n2 = min(idx2 + k // 2 - 1, la)\n",
    "                if n1 * a <= n2 * b:\n",
    "                    k -= n1 - idx1 + 1\n",
    "                    idx1 = n1 + 1\n",
    "                    # 此时 n1 对应的数 pivot1 = n1 * a 最多可以排除掉 2*k//2 - 1 <= k - 1\n",
    "                else:\n",
    "                    k -= n2 - idx2 + 1\n",
    "                    idx2 = n2 + 1\n",
    "                # print(k)\n",
    "\n",
    "        # print(r, getKth(r))\n",
    "        return (lcm * k % MOD + getKth(r) % MOD)%MOD\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        def gcd(a: int, b: int) -> int:\n",
    "            return gcd(b, a % b) if b else a\n",
    "        def lcm(a: int, b: int) -> int:\n",
    "            return a // gcd(a, b) * b\n",
    "        \n",
    "        ans = 0\n",
    "        maxVal = n * min(a, b)   # 最大值，到这里一定可以找到\n",
    "        l, r = 0, maxVal\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            if (m // a + m // b - m // lcm(a, b) >= n):  # 可以计算出这个区间内有多少个神奇的数\n",
    "                ans = m\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return ans % (pow(10, 9) + 7)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int: \n",
    "        lc = lcm(a, b)\n",
    "        l, r = min(a, b) - 1, min(a, b) * n + 1\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if n <= m // a + m // b - m // lc:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        l = min(a, b)\n",
    "        r = n * l\n",
    "        c = lcm(a, b)\n",
    "\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "\n",
    "            cnt = mid // a + mid // b - mid // c\n",
    "\n",
    "            if cnt >= n:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "            \n",
    "        return (r + 1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        left = 0\n",
    "        if b < a:\n",
    "            a, b = b, a\n",
    "        right = a * n\n",
    "        def gcd(a, b):\n",
    "            if b == 0:\n",
    "                return a\n",
    "            else: \n",
    "                return gcd(b, a % b)\n",
    "        lcm = int(a * b / gcd(a, b))\n",
    "        print(lcm)\n",
    "        def f(cur_num):\n",
    "            res = cur_num // a + cur_num // b - cur_num // lcm \n",
    "            return res\n",
    "        while left < right:\n",
    "\n",
    "            mid = left + (right - left) // 2\n",
    "            print(left, mid, right)\n",
    "            if f(mid) < n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left % (10 ** 9 + 7)\n",
    "    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        def gcd(a,b):\n",
    "            return a if b==0 else gcd(b,a%b)\n",
    "\n",
    "        def lcm(a,b):\n",
    "            return a//gcd(a,b)*b\n",
    "\n",
    "\n",
    "        lcm_ab=lcm(a,b)\n",
    "\n",
    "\n",
    "        l,r=0 ,n*min(a,b)\n",
    "\n",
    "        while l<=r:\n",
    "            m=(l+r)//2\n",
    "            if m//a+m//b-m//lcm_ab>=n:\n",
    "                ans=m\n",
    "                r=m-1\n",
    "            else:\n",
    "                l=m+1\n",
    "        return ans%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        l = min(a, b)\n",
    "        r = n * min(a, b)\n",
    "        c = lcm(a, b)\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            cnt = mid // a + mid // b - mid // c\n",
    "            if cnt >= n:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return (r + 1) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        # 能被a,b整除的数字是神奇的\n",
    "        # 返回神奇列表当中的第i个\n",
    "        min_bei = a*b//math.gcd(a,b)\n",
    "        def check(n):\n",
    "            return n//a + n//b - n//min_bei \n",
    "        left = 0 \n",
    "        right = 10**25+1 \n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left+right) >> 1\n",
    "            k = check(mid)\n",
    "            if k == n:\n",
    "                mid -= min(mid%a,mid%b,mid%min_bei)\n",
    "                return mid%(10**9+7)\n",
    "            elif k > n:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        def check(k):\n",
    "            cnt = 0\n",
    "            cnt += k // a \n",
    "            cnt += k // b \n",
    "            cnt -= k // math.lcm(a, b)\n",
    "            return cnt \n",
    "    \n",
    "        lo = 1 \n",
    "        hi = a * n + 1\n",
    "        while lo < hi:\n",
    "            mid = (lo+hi) // 2\n",
    "            if check(mid) < n:\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid \n",
    "        return lo%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        \"\"\"\n",
    "        解题思路\n",
    "            求第n个神奇数字，可以转换成一个数字当前是神奇数字，小于当前数字之前有n-1个神奇数字\n",
    "        :param n:\n",
    "        :param a:\n",
    "        :param b:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        lcm = math.lcm(a, b)\n",
    "        left, right = 0, min(a, b) * n\n",
    "\n",
    "        while  left +1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid // a + mid // b - mid // lcm >= n:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid \n",
    "        return right % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "      def gcd(a, b):\n",
    "        return a if b == 0 else gcd(b, a % b)\n",
    "      def check(x):\n",
    "        return x // a + x // b - x // c\n",
    "      c = a * b // gcd(a, b)\n",
    "      l, r = 0, 1e18\n",
    "      while l < r:\n",
    "        mid = (l + r) // 2\n",
    "        if check(mid) >= n:\n",
    "          r = mid\n",
    "        else:\n",
    "          l = mid + 1\n",
    "      return int(r % 1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        #公倍数函数 a*b//gcd(a,b)\n",
    "        #二分查找答案\n",
    "        #上下限 lcm(a,b)*n\n",
    "        #检查函数 a的数量+b的数量-lcm(a,b)的数量\n",
    "        MOD=10**9+7\n",
    "        def lcm(a:int,b:int)->int:\n",
    "            return a*b//gcd(a,b)\n",
    "\n",
    "        def check(a:int,b:int,c:int,t:int,n:int)->bool:\n",
    "            tot=t//a+t//b-t//c\n",
    "            return tot>=n\n",
    "\n",
    "        c=lcm(a,b)\n",
    "        l,r=0,c*n\n",
    "        while l+1<r:\n",
    "            m=l+(r-l)//2\n",
    "            if(check(a,b,c,m,n)): r=m\n",
    "            else: l=m\n",
    "        \n",
    "        return r%MOD\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lcm = math.lcm(a, b)\n",
    "        return bisect.bisect_left(range(a * n), n, key=lambda x: x // a + x // b - x // lcm) % int(1e9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        lo = min(a, b)\n",
    "        hi = (n + 1) * min(a, b)\n",
    "        c = lcm(a, b)\n",
    "        rank = lambda x: ceil(x / a) + ceil(x / b) - ceil(x / c)  # start from 1st\n",
    "        i = bisect_left(range(lo, hi), n, key=rank)\n",
    "        find = lo + i\n",
    "        # return the smallest x >= find and (x%a==0 or x%b==0)\n",
    "        return (min(ceil(find / a) * a, ceil(find / b) * b)) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "        l = min(a, b)\n",
    "\n",
    "        r = n * l\n",
    "\n",
    "        c = lcm(a, b)\n",
    "\n",
    "\n",
    "        while l <= r:\n",
    "\n",
    "            mid = (l + r) // 2\n",
    "\n",
    "            cnt = mid // a + mid // b - mid // c\n",
    "\n",
    "            if cnt >= n:\n",
    "\n",
    "                r = mid - 1\n",
    "\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        return (r + 1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "       lcm = math.lcm(a, b)\n",
    "       left, right = 0, min(a, b) * n  # 开区间 (left, right)\n",
    "       while left + 1 < right:  # 开区间不为空\n",
    "           mid = (left + right) // 2\n",
    "           if mid // a + mid // b - mid // lcm >= n:\n",
    "               right = mid  # 范围缩小到 (left, mid)\n",
    "           else:\n",
    "               left = mid  # 范围缩小到 (mid, right)\n",
    "       return right % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        def check(k):\n",
    "            cnt = 0\n",
    "            cnt += k // a \n",
    "            cnt += k // b \n",
    "            cnt -= k // math.lcm(a, b)\n",
    "            return cnt \n",
    "    \n",
    "        lo = 1 \n",
    "        hi = a * n + 1\n",
    "        while lo < hi:\n",
    "            mid = (lo+hi) // 2\n",
    "            if check(mid) < n:\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid \n",
    "        return lo%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        k = math.gcd(a, b)\n",
    "        m = a * b // k\n",
    "        c = a // k + b // k -1\n",
    "        p = n // c\n",
    "        n = n % c\n",
    "        ans = (p * m) % 1000000007\n",
    "        if n == 0:\n",
    "            return ans\n",
    "        else:\n",
    "            s, t = a, b\n",
    "            for i in range(n-1):\n",
    "                if s < t:\n",
    "                    s = s + a\n",
    "                else:\n",
    "                    t = t + b\n",
    "            return ((ans + min(s, t)) % 1000000007)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zxgbs(self,a,b):\n",
    "        while b:\n",
    "            a,b = b,(a%b)\n",
    "        return a\n",
    "\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        a,b = max(a,b),min(a,b)\n",
    "        gongbei = (a*b)/self.zxgbs(a,b)\n",
    "        i,j = 0,min(a,b)*n\n",
    "        while i < j:\n",
    "            mid = i + (j-i)//2\n",
    "            if mid // a + mid // b - mid // gongbei >= n:\n",
    "                j = mid \n",
    "            else:\n",
    "                i = mid +1\n",
    "        return j % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        lcm = math.lcm(a, b)\n",
    "        left, right = 0, min(a, b) * n  # 开区间 (left, right)\n",
    "        while left + 1 < right:  # 开区间不为空\n",
    "            mid = (left + right) // 2\n",
    "            if mid // a + mid // b - mid // lcm >= n:\n",
    "                right = mid  # 范围缩小到 (left, mid)\n",
    "            else:\n",
    "                left = mid  # 范围缩小到 (mid, right)\n",
    "        return right % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            if b==0:\n",
    "                return a\n",
    "            return gcd(b, a%b)\n",
    "        def lcm(a, b):\n",
    "            return a*b//gcd(a,b)\n",
    "        l = min(a,b)\n",
    "        r = n*l\n",
    "        ans = l\n",
    "        lcm = lcm(a,b)\n",
    "\n",
    "        while l<=r:\n",
    "            m = (r+l)//2\n",
    "            if (m//a+m//b-m//lcm)<n:\n",
    "                l = m+1\n",
    "            elif (m//a+m//b-m//lcm)>=n:\n",
    "                ans = m\n",
    "                r = m-1\n",
    "            \n",
    "        return ans%(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        lcm = math.lcm(a, b)\n",
    "        l, r = min(a, b), max(a, b) * n\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mid // a + mid // b - mid // lcm >= n: r = mid\n",
    "            else: l = mid + 1\n",
    "        return r % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        lcm_ = lcm(a, b)\n",
    "\n",
    "\n",
    "        def check(x):\n",
    "            return x // a + x // b - x // lcm_ >= n\n",
    "        \n",
    "        l, r = 1, min(a, b) * n\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return l % mod\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            return a if b == 0 else gcd(b, a % b)\n",
    "\n",
    "        def lcm(a, b):\n",
    "            return a // gcd(a, b) * b\n",
    "\n",
    "        lcm_ab = lcm(a, b)\n",
    "        ans = 0\n",
    "        # l = 0\n",
    "        # r = n * min(a, b)\n",
    "        # l......r\n",
    "        l, r = 0, n * min(a, b)\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            # 1....m\n",
    "            if m // a + m // b - m // lcm_ab >= n:\n",
    "                ans = m\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "\n",
    "        return ans % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left as bl\r\n",
    "class Solution:\r\n",
    "    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:\r\n",
    "        mod=1e9+7\r\n",
    "        maxn=max(a,b)\r\n",
    "        minn=min(a,b)\r\n",
    "        def gcd(a,b):\r\n",
    "            tmp=a%b\r\n",
    "            if tmp==0:\r\n",
    "                return b\r\n",
    "            else:\r\n",
    "                return gcd(b,tmp)\r\n",
    "        lcm=(maxn*minn)//gcd(maxn,minn)\r\n",
    "        nlcm=lcm//maxn+lcm//minn-1\r\n",
    "        nleft=n%nlcm\r\n",
    "        ans=bl(range(0,lcm),nleft,key=lambda x:x//maxn+x//minn)if nleft>0 else 0\r\n",
    "        ans=ans%mod+((lcm%mod)*(n//nlcm))%mod\r\n",
    "        return int(ans%mod)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
